The Viterbi decoding algorithm, known to be a maximum-likelihood algorithm, is widely used to decode convolutional codes. Convolutional coding is a bit-level coding technique rather than block-level techniques such as Reed-Solomon coding. In communication applications convolutional codes are advantages over block-level codes as the system gain degrades gracefully as the error rate increases, while block codes correct errors up to a point, after which the gain drops rapidly. Convolutional codes are decoded after an arbitrary length of data, while block codes introduce latency of an entire data block, convolutional codes do not require any block synchronization. Convolutionally encoded data is decoded through knowledge of the possible state transitions, created from the dependence of the current symbol on the past data. The allowable state transitions are represented by a trellis diagram. The Viterbi decoding algorithm involves the calculation of a Hamming distance between the received signal and the branches leading to each trellis state. At each trellis state, the path metric is stored. The actual decoding is accomplished by tracing the maximum likelihood path backwards through the trellis. A longer sequence results a more accurate reconstruction of the trellis such that in shorter sequences minimum path lengths give optimal results where in longer path lengths nearly all paths provide a solution as convergence is more and more attained. After a sequence of about five times the constraint length little accuracy is gained by additional inputs. The survivor path is determined during the trace back, and the output is generated. The number of trellis states amounts to 2k-1 with constraint length of k.
Most digital signal processors are designed to manipulate data having a fixed word size (e.g., 8-bit, 16-bit or 32-bit words). When the processor needs to manipulate non-standard word sizes the processor efficiency drops due the pipeline overhead for each retrieved bit. For example, when a 50 Mbit bit stream needs to be Viterbi error corrected a substantial percentage of the DSP is consumed by this single function.
In Viterbi decoding, on the forward pass, the minimum Hamming distance is accumulated and the survivor bit is stored for each state in each stage. Then the survivor bit path is generated during trace back. Conventional implementations can be in hardware or software. Hardware implementations are fast, able in some cases to accomplish trace back for each stage in a single cycle, but they are generally hardwired to a particular Viterbi application and not easily adapted to other applications. Software implementations are more flexible but much slower requiring many cycles of operation per stage in trace back. Attempts to increase speed generally resort to rearrangement or re-ordering of the accumulate-compare-select and trace back operations.